package graph

// dependencies like [['A','B'], ['B','C'], ['C','A']]
// check if there exists a circle dependencies
func checkCircle(dependencies [][]byte) bool {
	graph := make(map[byte][]byte)
	for _, dep := range dependencies {
		graph[dep[0]] = append(graph[dep[0]], dep[1])
	}

	visiting := make(map[byte]bool)
	visited := make(map[byte]bool)

	for node := range graph {
		if hasCycleDFS(graph, node, visiting, visited) {
			return true
		}
	}

	return false
}

func hasCycleDFS(graph map[byte][]byte, node byte, visiting, visited map[byte]bool) bool {
	if visiting[node] {
		return true
	}

	visiting[node] = true
	if !visited[node] {
		visited[node] = true
		if deps, exists := graph[node]; exists {
			for _, neighbor := range deps {
				if hasCycleDFS(graph, neighbor, visiting, visited) {
					return true
				}
			}
		}
	}
	delete(visiting, node)
	return false
}
